maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]

dirs = [
    lambda x, y: (x - 1, y),  # 上
    lambda x, y: (x, y + 1),  # 右
    lambda x, y: (x + 1, y),  # 下
    lambda x, y: (x, y - 1)  # 左
]


def maze_path(x1, y1, x2, y2):
    stack = []
    stack.append((x1, y1))
    while (len(stack) > 0):  # 栈空表示没有路
        current_node = stack[-1]  # 当前节点
        # 判断当前是否走到了终点
        if current_node[0] == x2 and current_node[1] == y2:
            # 把路径打印出来
            for p in stack:
                print(p)
            return True

        # x, y四个方向: x, y-1; x+1, y; x, y+1; x-1, y
        for dir in dirs:
            next_node = dir(current_node[0], current_node[1])
            # 如果下一个节点能走
            if maze[next_node[0]][next_node[1]] == 0:
                stack.append(next_node)
                maze[next_node[0]][next_node[1]] = 2  # 表示已经走过
                break
        else:  # 如果4个位置都不能走了，该点就出栈
            maze[current_node[0]][current_node[1]] = 2
            stack.pop()
    else:
        print("无路可走，走投无路")
        return False


maze_path(1, 1, 8, 8)
